import heapq
import math
from typing import List


class Solution:
    def isPossible(self, target: List[int]) -> bool:
        size = len(target)

        # 处理len(target)==1的情况：判断target[0]==1
        if size == 1:
            return target[0] == 1

        # 计算target的和
        # O(N)
        total = sum(target)

        # 将target转化为堆 O(N)
        target = [-num for num in target]
        heapq.heapify(target)

        while True:
            # 推出堆中最大值
            first_val = (-heapq.heappop(target))

            # 如果堆中最大值为1，则直接完成
            if first_val == 1:
                return True

            # 读取堆中第二大的值
            second_val = (-target[0])

            # 计算最大值每次逆操作减小的值
            minus = total - first_val

            # 如果第二大的值为1：判断最大的值能否减为1
            if second_val == 1:
                return (first_val - 1) % minus == 0

            # 计算需要逆操作多少次才可以令最大值小于等于第二大的值
            times = max(1, math.ceil((first_val - second_val) / minus))

            # 当前操作次数为0的情况
            if first_val - minus * times < 1:
                return False

            # 计算逆操作后的最大值
            first_val -= minus * times
            total -= minus * times

            # 将逆操作后的最大值添加回堆中
            heapq.heappush(target, (-first_val))


if __name__ == "__main__":
    print(Solution().isPossible([9, 3, 5]))  # True
    print(Solution().isPossible([1, 1, 1, 2]))  # False
    print(Solution().isPossible([8, 5]))  # True

    # 测试用例8/71 : True
    print(Solution().isPossible([1, 1000000000]))

    # 测试用例61/71 : False
    print(Solution().isPossible([2, 900000002]))

    # 测试用例16/71 : False
    print(Solution().isPossible([1, 1, 1, 6, 11, 16]))
